Lemme d'Euclide

Lemme d'Euclide

Soit $a$ et $b$ deux entiers naturels non nuls. Soit $r$ le reste dans la division euclidienne de $a$ par $b$ .
On a $\mathcal{D}(a;b)=\mathcal{D}(b;r)$ , et par conséquent, $\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r)$ .

Démonstration

On procède par double inclusion.

• $[\subset ]$  Montrons que $\mathcal{D}(a;b)\subset \mathcal{D}(b;r)$ .
  Soit $d\in \mathcal{D}(a;b)$ . Alors $d$ divise $a$ et $b$ , donc il existe des entiers $a^{\prime }$ et $b^{\prime }$ tels que $a=a^{\prime }d$ et $b=b^{\prime }d$ .
  En notant $q$ le quotient dans la division euclidienne de $a$ par $b$ , on a alors : $\begin{array}{rl}a=bq+r& ⟺a^{\prime }d=b^{\prime }dq+r⟺d(a^{\prime }-b^{\prime }q)=r\end{array}$  
  donc $d$ divise $r$ , donc $d\in \mathcal{D}(b;r)$ .
  Ceci étant valable pour tout $d\in \mathcal{D}(a;b)$ , on en déduit que $\mathcal{D}(a;b)\subset \mathcal{D}(b;r)$ .
  
• $[\supset ]$ Montrons que $\mathcal{D}(b;r)\subset \mathcal{D}(a;b)$ .
  Soit $d\in \mathcal{D}(b;r)$ . Alors $d$ divise $b$ et $r$ , donc il existe des entiers $b^{\prime }$ et $r^{\prime }$ tels que $b=b^{\prime }d$ et $r=r^{\prime }d$ .
  En notant $q$ le quotient dans la division euclidienne de $a$ par $b$ , on a alors : 
  $\begin{array}{rl}a=bq+r& ⟺a=b^{\prime }dq+r^{\prime }d⟺d(b^{\prime }q+r^{\prime })=a\end{array}$  
  donc $d$ divise $a$ , donc $d\in \mathcal{D}(a;b)$ .
  Ceci étant valable pour tout $d\in \mathcal{D}(b;r)$ , on en déduit que $\mathcal{D}(b;r)\subset \mathcal{D}(a;b)$ .

On en déduit que $\mathcal{D}(a;b)=\mathcal{D}(b;r)$ .

Comme $a$ et $b$ sont non nuls, les ensembles $\mathcal{D}(a;b)$ et $\mathcal{D}(b;r)$ admettent un plus grand élément (qui est le même puisque ces ensembles sont égaux), c'est-à-dire que l'on a $\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r)$ .